#pragma warning (push)
#pragma warning (disable: 4996)

#include <string>
#include <boost/xpressive/xpressive.hpp>
#include <boost/type_traits/is_same.hpp>

#pragma warning (pop)

namespace SmsAlg {

    /**
    * \struct  natural_sort
    *
    * \brief   This functor sorts strings in a natural way e.g. "abc10def", "abc1def" "abc02def" 
    * 			will be sorted to "abc1def", "abc02def", "abc10def". 
    *
    */

    template< typename C = std::less< std::string >, unsigned int padding_length = 10 >
    struct natural_sort : public std::binary_function < typename C::first_argument_type, typename C::first_argument_type, bool > {

        BOOST_STATIC_ASSERT( ( boost::is_same< typename C::first_argument_type, typename C::second_argument_type >::value ) );
        BOOST_STATIC_ASSERT( ( boost::is_same< typename C::result_type, bool >::value ) );

        typedef C comparator_type;
        typedef typename comparator_type::first_argument_type string_type;
        typedef boost::xpressive::smatch match_results;
        typedef boost::xpressive::sregex_iterator regex_iterator;
        typedef boost::xpressive::sregex regex_type;

        natural_sort() {
            regex = boost::xpressive::sregex::compile( "(\\d+)|([^\\d]+)" );
        }

        bool operator()( const string_type &l, const string_type &r ) {
            for( regex_iterator lit( l.begin(), l.end(), regex ), rit( r.begin(), r.end(), regex ), end;
                lit != end && rit != end; ++lit, ++rit )
                if ( compare( *lit, *rit ) )
                    return true;
                else if ( compare( *rit, *lit ) )
                    return false;
            return false;
        }

    private:
        comparator_type comp;
        regex_type regex;
        bool compare( const match_results &l, const match_results &r ) {
            if ( !l[ 1 ].str().empty() && !r[ 1 ].str().empty() )
                return comp( pad( l.str() ), pad( r.str() ) );
            else
                return comp( l.str(), r.str() );
        }
        string_type pad( const string_type &s ) {
            return string_type( padding_length - s.length(), '0' ) + s;
        }
    };


}

